"""
带体积的01背包问题
"""

weights = [None, 2, 3, 4, 7]
volumns = [None, 3, 2, 1, 1]
values = [None, 1, 3, 5, 9]

maxWeight = 10
maxVolumn = 5
maxItem = 4


def DP():
    dp = {}
    solution = {}

    # k=1
    for c in range(0, maxVolumn + 1):
        for w in range(0, maxWeight + 1):
            # 对于只考虑k=1的情况，能放则放1个，否则放0个。
            if c >= volumns[1] and w >= weights[1]:
                sol = True
            else:
                sol = False
            solution[1, c, w] = sol
            dp[1, c, w] = int(sol) * values[1]
    # c=0
    for k in range(1, maxItem + 1):
        for w in range(0, maxWeight + 1):
            dp[k, 0, w] = 0
            solution[k, 0, w] = False
    # w=0
    for k in range(1, maxItem + 1):
        for c in range(0, maxVolumn + 1):
            dp[k, c, 0] = 0
            solution[k, c, 0] = False

    for k in range(2, maxItem + 1):
        for c in range(1, maxVolumn + 1):
            for w in range(1, maxWeight + 1):
                max_value = dp[k - 1, c, w]  # 不含物品k
                sol = False
                if c - volumns[k] >= 0 and w - weights[k] >= 0:
                    temp = dp[k - 1, c - volumns[k],
                              w - weights[k]] + values[k]
                    if temp > max_value:
                        max_value = temp
                        sol = True
                dp[k, c, w] = max_value
                solution[k, c, w] = sol
    # PrintDP(dp)
    # PrintDP(solution)
    TrackSolution(dp, solution)


def PrintDP(dp):
    for k in range(1, maxItem + 1):
        print(k)
        for c in range(0, maxVolumn + 1):
            for w in range(0, maxWeight + 1):
                print('', dp[k, c, w], end='')
            print()


def TrackSolution(dp, solution):
    c = maxVolumn
    w = maxWeight
    ans = []
    # 逆着追溯答案。
    for k in range(maxItem, 0, -1):
        hasK = solution[k, c, w]
        ans.append(hasK)
        if hasK:
            c -= volumns[k]
            w -= weights[k]
    ans.reverse()
    print(ans)
    print(dp[maxItem, maxVolumn, maxWeight])


DP()